/* -*- mode: c++; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 4 -*- */
/* vi: set expandtab shiftwidth=4 tabstop=4: */

#include "Hashes.h"
#include <unistd.h>
#include <stdint.h>

#include <string>
#include <map>
#include <iostream>
#include <iomanip>
using namespace std;

#include <set>
using std::set;

#include <math.h>
class RandomString {
public:
    virtual const string& next() = 0;
    virtual ~RandomString()
    {
    }
};

class RandomBits : public RandomString {
private:
    string str;
    uint32_t buf[4];
public:
    RandomBits(int seed)
    {
        srandom(seed);
    }

    const string& next()
    {
        for (size_t i = 0; i < sizeof(buf)/sizeof(uint32_t); ++i) {
            buf[i] = random();
        }
        str.assign((const char*) buf, sizeof(buf));
        return str;
    }
};

/**
 *
 *  A, B ... Z
 *  AA, BA, CA, ... ZA,
 *  AB, BB, CB.... ZZ
 *  AAA, BAA,....
 */
class AsciiIteration : public RandomString
{
public:
    string data;
    char cmin;
    char cmax;
    AsciiIteration(string start="", char letter_min='A', char letter_max='z')
        :  data(start), cmin(letter_min), cmax(letter_max)
    {
        if (start.empty()) {
            data = cmin - 1;
        }
    }

    const string& next()
    {
        for (size_t i = 0; i < data.size(); ++i) {
            data[i]++;
            if (data[i] > cmax) {
                data[i] = cmin;
                if (i == data.size() -1) {
                    data += cmin;
                }
            } else {
                break;
            }
        }
        return data;
    }
};

class AsciiIteration2 : public RandomString
{
public:
    string data;
    const char cmin;
    const char cmax;
    AsciiIteration2(const string& start="", char letter_min='A', char letter_max='z')
        : data(start), cmin(letter_min), cmax(letter_max)
    {
        if (start.empty()) {
            data = (cmin - 1);
        }
    }
    const string& next()
    {
        for (int i = data.size() -1 ; i >= 0; --i) {
            data[i]++;
            if (data[i] > cmax) {
                data[i] = cmin;
                if (i == 0) {
                    data += cmin;
                }
            } else {
                break;
            }
        }
        return data;
    }
};

// long strings of A (repeated n time) [A-z]
// after it gets too long it becomes B (repeated n times) [A-z]
class AsciiIteration3 : public RandomString
{
public:
    string data;
    char cmin;
    char cmax;

    AsciiIteration3(string start="", char letter_min='A', char letter_max='z')
        : data(start), cmin(letter_min), cmax(letter_max)
    {
        if (start.empty()) {
            data = cmin;
            data += cmin;
        }
    }

    const string& next()
    {
        int i = data.size()-1;
        data[i]++;
        if (data[i] > cmax) {
            data[i] = data[0];
            data += data[0];
            if (data.size() > 12) {
                data = data[0] +1;
                data += cmin;
            }
        }
        return data;
    }
};

template<class HASH>
double findcollision(RandomString* rs, const HASH& hasher, uint32_t mask)
{
    map<uint32_t,string> hashset;
    uint32_t count = 1;
    int last = 0;
    int pow2 = 1;
    int exponent = 0;
    //uint32_t data[12];
    //char data[48];
    //uint32_t d =random();
    while (exponent < 21) {
        //cout << "trying exponent = " << exponent << "\n";
        for (int j =last; j < pow2; ++j) {
            /*
              for (int k = 0; k < 12; ++k) {
              data[k] = ((count + k));// +d) % (26*2)) + 65;
              d *= 21;
              }
            */
            const string& s = rs->next();
            uint32_t h = hasher.hashStr(s.data(), s.size());
            h &= mask;

            //cout << "s = " << s << ", hash = " << h << "\n";
            map<uint32_t,string>::iterator i = hashset.find(h);
            if (i != hashset.end()) {
                if (s == i->second) {
                    cout << "error... we hashed the same key! " << s << "\n";
                    exit(1);
                }
#ifdef DEBUG
                cout << "collision at 2^" << log2(count) << ", current=" << s << ", orig = " <<  i->second << "\n";
#endif
                return log2(count);
            } else {
                hashset[h] = s;
            }
            count++;
        }

        last = pow2;
        pow2 *= 2;
        exponent++;
    }
    return exponent;
}

template<class HASH>
void run(uint32_t mask, uint32_t seed, const HASH& hash)
{

    cout << setw(30) << hash.name() << "\t" << flush;
    {
        AsciiIteration i("", 'A', 'z');
        double d = findcollision(&i, hash, mask);
        cout << fixed << setw(7) << setprecision(1) << d << "\t" << flush;
    }

    {
        AsciiIteration2 i("DEADBEEF", 'A', 'z');
        double d = findcollision(&i, hash, mask);
        cout << fixed << setw(7) << setprecision(1) << d << "\t" << flush;
    }

    {
        AsciiIteration3 i;
        double d = findcollision(&i, hash, mask);
        cout << fixed << setw(7) << setprecision(1) << d << flush;
    }

    {
        RandomBits i(seed);
        double d = findcollision(&i, hash, mask);
        cout << fixed << setw(7) << setprecision(1) << d << flush;
    }
    cout << endl;

}

int main(int argc, char * const argv[])
{
    int ch;
    uint32_t bits = 32;
    int seed = 1;
    while ((ch = getopt(argc, argv, "b:s:")) != -1) {
        switch (ch) {
        case 's':
            seed = strtol(optarg, 0, 10);
            break;
        case 'b':
            bits = strtol(optarg, 0, 10);
            break;
        case '?':
        default:
            cerr << "whatever";
            exit(1);
        }
    }
    argc -= optind;
    argv += optind;

    uint32_t mask = 0;
    for (uint32_t i = 0; i < bits; ++i) {
        mask |= (1 << i);
    }
    cout << hex << mask << "\t" << dec << mask << endl;

    run(mask, seed, Times33());
    run(mask, seed, PaulHsiehHash32());
    run(mask, seed, NGalbreathHash32_random16());
    run(mask, seed, NGalbreathHash32_xorplus1());
    run(mask, seed, ThomasWangHash32_Jan2007());
    run(mask, seed, ThomasWangHash32_Jan2007_alt());
    run(mask, seed, ThomasWangHash32_orig());
    run(mask, seed, ThomasWangHash32_mult());
    run(mask, seed, FNVHash32());
    run(mask, seed, RobertJenkinsHash32());
    run(mask, seed, BobJenkins_lookup3());

    return 0;
}
